package com.maduar.demo.algo.interview;

import java.util.Stack;

/**
 * Description:
 *
 * @author maduar maduar@163.com
 * @date 2021-03-13 16:08
 */
public class SimpleInterview {

    /**
     * 1. 接口名称: 回文数
     * 2. 接口文档编号:
     * 3. 接口详细说明: 给你一个整数 x ，如果 x 是一个回文整数，返回 true ；否则，返回 false 。
     * 回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。例如，121 是回文，而 123 不是。
     *
     * @param
     * @return
     * @Author: danny.pang
     * @Date: 2021-03-13 16:09:15
     */
    public static boolean isPalindrome(int x) {
        if (x < 0 || (x % 10 == 0 && x != 0)) {
            return false;
        }

        int revertNumber = 0;
        while (x > revertNumber) {
            revertNumber = revertNumber * 10 + x % 10;
            x /= 10;
        }

        return x == revertNumber || x == revertNumber / 10;
    }

    /**
     * 1. 接口名称:
     * 2. 接口文档编号:
     * 3. 接口详细说明:
     *
     * @param
     * @return
     * @Author: danny.pang
     * @Date: 2021-03-13 16:51:50
     */
    public static int romanToInt(String s) {
        int len = s.length();
        if (len == 1) {
            return getRomValue(s.charAt(0));
        }

        int result = 0;

        for (int i = 0; i < len - 1; i++) {
            int current = getRomValue(s.charAt(i));
            int next = getRomValue(s.charAt(i + 1));
            result = current < next
                    ? result - current
                    : result + current;
        }

        return result + getRomValue(s.charAt(len - 1));
    }


    /**
     * 1. 接口名称:
     * 2. 接口文档编号:
     * 3. 接口详细说明:
     *
     * @param
     * @return
     * @Author: danny.pang
     * @Date: 2021-03-13 17:29:47
     */
    public static String longestCommonPrefix(String[] strs) {
        int len = strs.length;

        if(len == 0) {
            return "";
        }

        if(len == 1) {
            return strs[0];
        }

        int strLength = strs[0].length();
        for (int i = 0; i < strLength; i++) {
            char c = strs[0].charAt(i);
            for (int j = 1; j < len; j++) {
                if (strs[j].length() == i || strs[j].charAt(i) != c) {
                    return strs[0].substring(0, i);
                }
            }
        }

        return strs[0];
    }


    /**
     * 1. 接口名称: 有效的括号
     * 2. 接口文档编号:
     * 3. 接口详细说明:
     *
     * @param
     * @return
     * @Author: danny.pang
     * @Date: 2021-03-13 17:57:02
     */
    public static boolean isValid(String s) {
        int length = s.length();
        if (length == 0 || length % 2 != 0) {
            return false;
        }

        Stack<Character> a = new Stack<>();

        for (int i = 0; i < length; i++) {
            char c = s.charAt(i);
            int tmp = getValidValue(c);

            if (tmp == 0) {
                return false;
            }

            if (tmp <= 3) {
                a.push(c);
            } else {
                if (a.isEmpty()) {
                    return false;
                }

                char b = a.pop();
                if (getValidValue(b) != tmp - 3) {
                    return false;
                }
            }
        }

        return a.isEmpty();
    }

    /**
     * 1. 接口名称: 删除数组中的重复项
     * 2. 接口文档编号:
     * 3. 接口详细说明:
     *
     * @param
     * @return
     * @Author: danny.pang
     * @Date: 2021-03-14 15:31:23
     */
    public static int removeDuplicates(int[] nums) {
        int len = nums.length;
        if(len < 2) {
            return len;
        }

        int index = 0;
        for (int i = 1; i < len; i++) {
            if (nums[i] - nums[i - 1] != 0) {
                index++;
                nums[index] = nums[i];
            }
        }

        return index + 1;
    }

    /**
     * 1. 接口名称: indexOf
     * 2. 接口文档编号:
     * 3. 接口详细说明:
     *
     * @param
     * @return
     * @Author: danny.pang
     * @Date: 2021-03-14 16:04:44
     */
    public static int strStr(String haystack, String needle) {
        int aLength = haystack.length();
        int bLength = needle.length();

        if (bLength == 0) {
            return 0;
        } else if (aLength < bLength) {
            return -1;
        }

        char c = needle.charAt(0);
        int privot = 0;
        int index = 0;
        while (index <= aLength - bLength) {
            if (haystack.substring(index, index + bLength).equals(needle)) {
                return index;
            }
            index++;
        }

        return -1;
    }

    /**
     * 1. 接口名称:
     * 2. 接口文档编号:
     * 3. 接口详细说明:
     *
     * @param
     * @return
     * @Author: danny.pang
     * @Date: 2021-03-14 17:44:22
     */
    public static String countAndSay(int n) {
        if (n == 1) {
            return "1";
        }

        return null;
    }

    public static int getValidValue(char ch) {
        switch(ch) {
            case '{': return 1;
            case '(': return 2;
            case '[': return 3;
            case '}': return 4;
            case ')': return 5;
            case ']': return 6;
            default: return 0;
        }
    }

    /**
     * 1. 接口名称:  最大子序列
     * 2. 接口文档编号:
     * 3. 接口详细说明:
     *
     * @param
     * @return
     * @Author: danny.pang
     * @Date: 2021-03-14 18:14:27
     */
    public static int maxSubArray(int[] nums) {
        int len = nums.length;
        if(len == 0) {
            return 0;
        } else if(len == 1){
            return nums[0];
        }

        int index = 1;
        int ans = nums[0];
        int sum = nums[0];
        while(index < len) {
            int current = nums[index];
            if(sum > 0) {
                sum += current;
            } else {
                sum = current;
            }

            ans = Math.max(ans, sum);
            index++;
        }

        return ans;
    }


    /**
     * 1. 接口名称:
     * 2. 接口文档编号:
     * 3. 接口详细说明:
     *
     * @param
     * @return
     * @Author: danny.pang
     * @Date: 2021-03-14 18:26:34
     */
    public static int lengthOfLastWord(String s) {
        int len = s.length();
        if(len == 0) {
            return 0;
        }

        int count = 0;
        int index = len - 1;

        while(index >= 0) {
            if (s.charAt(index) == ' ') {
                if (count != 0) {
                    return count;
                }
                index--;
            } else {
                index--;
                count++;
            }
        }

        return count;
    }

    public static int getRomValue(char ch) {
        switch(ch) {
            case 'I': return 1;
            case 'V': return 5;
            case 'X': return 10;
            case 'L': return 50;
            case 'C': return 100;
            case 'D': return 500;
            case 'M': return 1000;
            default: return 0;
        }
    }



}
